package pers.sloera.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Collections;

/**
 * 下一个更大元素 III
 *
 * @author sloera
 * @date 2022-07-03 20:54:06
 */
class NextGreaterElementIii {
    public static void main(String[] args) {
        Solution solution = new NextGreaterElementIii().new Solution();
        System.out.println(solution.nextGreaterElement(230241));
        System.out.println(solution.nextGreaterElement(123));
        System.out.println(solution.nextGreaterElement(21));
        System.out.println(solution.nextGreaterElement(12));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int nextGreaterElement(int n) {
            char[] chars = String.valueOf(n).toCharArray();
            int right, left = chars.length - 2;
            while (left >= 0) {
                right = chars.length - 1;
                while (right > left && chars[left] >= chars[right]) {
                    right--;
                }
                if (right > left) {
                    char temp = chars[right];
                    chars[right] = chars[left];
                    chars[left] = temp;
                    sort(chars, left + 1, chars.length - 1);
                    long l = Long.parseLong(new String(chars));
                    if (l <= Integer.MAX_VALUE) {
                        return (int) l;
                    }
                }
                left--;
            }
            return -1;
        }

        private void sort(char[] chars, int left, int right) {
            if (right - left <= 0) {
                return;
            }
            ArrayList<Character> list = new ArrayList<>();
            for (int i = left; i <= right; i++) {
                list.add(chars[i]);
            }
            Collections.sort(list);
            for (int i = left; i <= right; i++) {
                chars[i] = list.get(i - left);
            }
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}
